/**
 * https://leetcode.cn/problems/delete-and-earn/submissions/566658792/
 * 740. 删除并获得点数
 * medium 2024.09.21
 * 多维dp
 */

class Solution {
public:
    // typedef long long ll;
    const int m=1e4+2;
    int deleteAndEarn(vector<int>& nums) {
        vector<int>dp(m,0);
        int maxt=2;
        for(auto x:nums){
            dp[x]+=x;
            if(x>maxt)
            maxt=x;
        }
        int sum=0;
        for(int i=2;i<=maxt+1;++i){
            if(dp[i]==0){
                sum+=max(dp[i-1],dp[i-2]);
                dp[i-1]=0;
            }else
            dp[i]=max(dp[i-1],dp[i-2]+dp[i]);
        }
        return sum;
    }
};